In a communications network, there is a well-recognized need to classify information units, such as packets, that are passed between the various network devices in the network, e.g., routers and switches, in order to support a wide range of applications, such as security control, packet filtering, Class of Service (CoS) and Quality of Service (QoS). Often in such networks, these network devices use access control lists (ACLs) to, inter alia, classify packets for these applications.
An ACL typically comprises an ordered list of access control entries (ACEs), i.e., rules, where each rule defines a pattern (criterion) that is compared with received packets. The pattern could specify a particular source or destination address, a protocol or some other field that is looked for in the packet. For example, the pattern might be defined to look for a specific protocol in the packet's header such as, the Transmission Control Protocol (TCP) or the Internet Protocol (IP). The pattern is used to determine if the rule applies to the packet. If the pattern is found in the packet, the rule is said to apply to the packet.
Associated with each rule is an action that specifies the act to be taken if the rule applies. In its simplest form, this action may be to allow the matched packet to proceed towards its destination, i.e., “permit,” or to stop the packet from proceeding any further, i.e., “deny.” Conversely, if there is no match to any of the ACL's rules, the action may be to drop the packet, i.e., “a final deny.” In a more sophisticated form, complex policies and filtering rules may be implemented in the ACL to determine the course of the data packet.
Typically, a packet is classified by searching for the first rule in the ACL that applies to the packet. The number of rules involved and the amount of processing time needed to make this determination often depends on the approach taken. For example, one approach would be to run through the list of rules starting from the first rule in the list and continuing towards the last rule in the list until a matching rule, i.e., a rule that applies to the packet, is found. This approach is simple, but is not very efficient. For example, the time spent processing each packet may vary depending on the packet. Packets that meet the criteria associated with rules earlier in the list will be processed faster than packets that meet criteria associated with rules that are positioned farther down the list.
One approach to obtaining an overall faster processing of packets is to predetermine the frequency of the matching of the various rules and to place the most selected rules at the top of the list. However, this method is highly dependent on the packet mix and is not very efficient should this mix change. Another approach is to implement a technique whereby packets are classified using a predetermined number of lookup operations such as described in McRae1.
McRae1 describes a technique whereby a packet's header is divided into sections. These sections are applied to a hierarchy of lookup tables that represent all possible combinations of matching rules for all values of the packet header sections to determine an outcome such as, e.g., a first matching rule that applies to the packet. These lookup tables must exist before a packet can be classified. Computing resources, such as processor time and memory, needed to generate these lookup tables depends in part on the number of rules in the ACL. Generally, as the number of rules in the ACL increases, the computing resources needed to build and hold the lookup tables increases. In systems where computing resources are limited, the number of rules that the technique can support may be limited due to the limited resources available.
McRae2, discloses an arrangement in which successive lookup tables, after the first set of tables, are compiled at runtime in response to the characteristics of packets being classified. This materially reduces compilation time and also saves memory space corresponding to classification rules that are not needed for the packets entering the router. The arrangement described in McRae1 is often termed “TurboACL,” as is the related arrangement described in McRae2.
However, with the ever-increasing number of classification rules and the increasing diversity of packet characteristics, available memory space is still a problem. A table below the top level may require a very large block of contiguous memory locations. This may stall compilation because of a limitation of memory recourses.